EDPC V - Subtree - Atcoder-myReflection-blueberry

EDPC V - Subtree

Difficulty:None

問題

各頂点を白か黒で塗る方法であって、頂点$ iが黒であり、黒である頂点が連結であるような塗り方を$ 1 \leq i\leq Nそれぞれについて数え上げよ

解法

全方位木DPをする。子を黒く塗る場合の塗り方+1（部分木をすべて白にする場合）

実装

code:cpp

ll n,m;

using Data = long long;

using Cost = long long;

Data merge(Data a, Data b) { return a*b%m; }

Data e() { return 1; }

Data leaf() { return 1; }

Data apply(Data a, int c, int, Cost w) { return a+1; }

bool solve(){

cin >> n >> m;

Rerooting<Cost,Data,merge,e,leaf,apply>g(n);

rep(i,n-1){

LL(a,b);

a--,b--;

g.add_edge(a,b,1);

g.add_edge(b,a,1);

}

auto ans = g.run();

rep(i,n){

cout<<ansi<<endl;

}

return false;

}